#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 判断字符串是否为回文串
int isPalindrome(char *inputString) {
    int stringLength = strlen(inputString);
    for (int i = 0; i < stringLength / 2; i++) {
        if (inputString[i]!= inputString[stringLength - i - 1]) {
            return 0;
        }
    }
    return 1;
}

// 辅助函数，用于反转字符串
void reverseString(char *stringToReverse) {
    int length = strlen(stringToReverse);
    for (int i = 0; i < length / 2; i++) {
        char temp = stringToReverse[i];
        stringToReverse[i] = stringToReverse[length - i - 1];
        stringToReverse[length - i - 1] = temp;
    }
}

// 尝试从左边添加字符形成回文串并返回最短结果（若存在）
char *makePalindromeByAddingLeft(char *originalString) {
    int originalLength = strlen(originalString);
    char *shortestResult = NULL;
    for (int prefixLength = 0; prefixLength < originalLength; prefixLength++) {
        // 取出前缀子串
        char *prefixSubstring = (char *)malloc((prefixLength + 1) * sizeof(char));
        strncpy(prefixSubstring, originalString, prefixLength + 1);
        prefixSubstring[prefixLength + 1] = '\0';

        // 复制原字符串
        char *newString = (char *)malloc((originalLength + strlen(prefixSubstring) + 1) * sizeof(char));
        strcpy(newString, originalString);

        // 反转前缀子串
        reverseString(prefixSubstring);
        // 将反转后的前缀子串拼接到原字符串末尾
        strcat(newString, prefixSubstring);

        if (isPalindrome(newString)) {
            // 如果是回文串，更新最短结果
            if (shortestResult == NULL || strlen(newString) < strlen(shortestResult)) {
                if (shortestResult!= NULL) {
                    free(shortestResult);
                }
                shortestResult = (char *)malloc((strlen(newString) + 1) * sizeof(char));
                strcpy(shortestResult, newString);
            }
        }

        free(prefixSubstring);
        free(newString);
    }
    return shortestResult;
}

// 尝试从右边添加字符形成回文串并返回最短结果（若存在）
char *makePalindromeByAddingRight(char *originalString) {
    int originalLength = strlen(originalString);
    char *shortestResult = NULL;
    for (int suffixStartIndex = originalLength - 1; suffixStartIndex >= 0; suffixStartIndex--) {
        // 取出后缀子串
        char *suffixSubstring = (char *)malloc((originalLength - suffixStartIndex + 1) * sizeof(char));
        strcpy(suffixSubstring, originalString + suffixStartIndex);

        // 复制原字符串
        char *newString = (char *)malloc((originalLength + strlen(suffixSubstring) + 1) * sizeof(char));
        strcpy(newString, suffixSubstring);

        // 反转后缀子串
        reverseString(suffixSubstring);
        // 将反转后的后缀子串拼接到原字符串开头
        strcat(newString, originalString);

        if (isPalindrome(newString)) {
            // 如果是回文串，更新最短结果
            if (shortestResult == NULL || strlen(newString) < strlen(shortestResult)) {
                if (shortestResult!= NULL) {
                    free(shortestResult);
                }
                shortestResult = (char *)malloc((strlen(newString) + 1) * sizeof(char));
                strcpy(shortestResult, newString);
            }
        }

        free(suffixSubstring);
        free(newString);
    }
    return shortestResult;
}

// 找到使字符串成为回文串需要添加的最小字符串，同时考虑左右添加两种情况
char *makePalindrome(char *inputString) {
    if (isPalindrome(inputString)) {
        // 如果本身就是回文串，直接返回原字符串的副本
        char *result = (char *)malloc((strlen(inputString) + 1) * sizeof(char));
        strcpy(result, inputString);
        return result;
    }

    char *leftResult = makePalindromeByAddingLeft(inputString);
    char *rightResult = makePalindromeByAddingRight(inputString);

    // 比较左右添加得到的结果，选择更短的那个
    if (leftResult == NULL) {
        return rightResult;
    }
    if (rightResult == NULL) {
        return leftResult;
    }
    if (strlen(leftResult) < strlen(rightResult)) {
        free(rightResult);
        return leftResult;
    }
    free(leftResult);
    return rightResult;
}

int main() {
    char input[100];  // 假设输入的字符串长度不超过100，可根据实际调整大小
    while (1) {  // 循环接收输入
        printf("请输入一个字符串（输入exit退出程序）：");
        scanf("%s", input);
        if (strcmp(input, "exit") == 0) {  // 判断是否输入exit，若是则退出循环
            break;
        }
        char *palindrome = makePalindrome(input);
        printf("添加字符后形成的回文串为: %s\n", palindrome);
        free(palindrome);
    }
    return 0;
}